package com.atcumt.Carl.String;

import java.util.List;

public class String02 {

    /**
     * 单词替换 - 字典树
     */
    public String replaceWords(List<String> dictionary, String sentence) {

        for (String s : dictionary) {
            add(s);
        }
        StringBuilder sb = new StringBuilder();
        String[] strs = sentence.split(" ");
        for (String str : strs) {
            sb.append(search(str)).append(" ");
        }
        return sb.substring(0, sb.length() - 1);
    }

    TrieNode root = new TrieNode();
    private void add(String s) {
        TrieNode p = root;
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if (p.nodes[idx] == null) {
                p.nodes[idx] = new TrieNode();
            }
            p = p.nodes[idx];
        }
        p.isEnd = true;
    }

    private String search(String s) {
        TrieNode p = root;
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if (p.nodes[idx] == null) {
                break;
            }
            if (p.nodes[idx].isEnd) {
                return s.substring(0, i + 1);
            }
            p = p.nodes[idx];
        }
        return s;
    }
}

class TrieNode {
    boolean isEnd;
    TrieNode[] nodes = new TrieNode[26];
}
